package com.buddy.learn.algorithm.simple;

import java.util.ArrayList;
import java.util.Stack;

/**
 * 二叉树
 * 二叉树与数组：
 * 使用数组存储时，会按照层级顺序把二叉树的节点放到数组中对应的位置上，
 * 如果某一个节点的 Left 或者 Right 空缺，则数组的位置也会相应的空出来
 * <p>
 * parent 的 Left index = 2*parent+1 ；Right index=2*parent+2
 * leftChild 的 parent = (leftChild -1)/2
 *
 * @author Buddy
 * @date 2021/4/20
 */
public class _二叉树之字遍历 {

    private class Node {
        int data;
        Node left;
        Node right;

        Node(int data, Node left, Node right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }

    private Node init() {
        // 必须逆序建立，因为上面的节点会用到下面的子节点
        Node N = new Node(7, null, null);
        Node H = new Node(6, null, null);
        Node E = new Node(5, H, N);
        Node D = new Node(4, null, null);
        Node C = new Node(3, null, null);
        Node B = new Node(2, D, E);
        Node A = new Node(1, B, C);
        return A;
    }


    public static void main(String[] args) {
        _二叉树之字遍历 binaryTree = new _二叉树之字遍历();
        Node root = binaryTree.init();
        System.out.println(zigzagLevelOrder(root));
    }

    private static ArrayList<ArrayList<Integer>> zigzagLevelOrder(Node root) {
        Node c = root;
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        if (c == null) {
            return res;
        }
        Stack<Node> s1 = new Stack<>();
        Stack<Node> s2 = new Stack<>();

        s1.push(root);
        while (!s1.isEmpty() || !s2.isEmpty()) {
            ArrayList<Integer> tmp = new ArrayList<>();
            while (!s1.isEmpty()) {
                c = s1.pop();
                tmp.add(c.data);
                if (c.left != null) {
                    s2.push(c.left);
                }
                if (c.right != null) {
                    s2.push(c.right);
                }
            }
            res.add(tmp);
            tmp = new ArrayList<>();
            while (!s2.isEmpty()) {
                c = s2.pop();
                tmp.add(c.data);
                if (c.right != null) {
                    s1.push(c.right);
                }
                if (c.left != null) {
                    s1.push(c.left);
                }
            }
            if (!tmp.isEmpty()) {
                res.add(tmp);
            }
        }
        return res;
    }


}
